package ercahshu

func inorderTraversal(root *TreeNode) []int {
	// 确定输入和返回值，确定边界条件，确定单层逻辑
	ans := make([]int, 0)
	stack := make([]*TreeNode, 0)
	node := root
	for node != nil || len(stack) > 0 {
		for node != nil {
			stack = append(stack, node)
			node = node.Left
		}
		ans = append(ans, stack[len(stack)-1].Val)
		node = stack[len(stack)-1].Right
		stack = stack[:len(stack)-1]
	}
	return ans
}
